package 牛客_面试必刷.Month07.day10;

public class 在二叉树中找到两个节点的最近公共祖先 {
    //这里写的没问题，但是时间复杂度通不过
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) return 0;
        if(root.val == o1 || root.val == o2) return root.val;
        if(find(root.left,o1)  && find(root.left,o2)) return lowestCommonAncestor(root.left,o1,o2);
        if(find(root.right,o1) && find(root.right,o2)) return lowestCommonAncestor(root.right,o1,o2);
        return root.val;
    }

    public boolean find(TreeNode p,int val){
        if(p == null) return false;
        if(p.val == val) return true;
        return find(p.left,val) || find(p.right,val);
    }
}

/*
public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) return -1;
        if(root.val == o1 || root.val == o2) return root.val;
        int left = lowestCommonAncestor(root.left,o1,o2);
        int right = lowestCommonAncestor(root.right,o1,o2);
        if(left == -1) return right;
        if(right == -1) return left;
        return root.val;
    }



*/
